Analyzing Selected Quantified Integer Programs
Identifieur interne : 006C38 ( Main/Exploration ); précédent : 006C37; suivant : 006C39Analyzing Selected Quantified Integer Programs
Auteurs : K. Subramani [États-Unis]Source :
- Lecture Notes in Computer Science [ 0302-9743 ]
Abstract
Abstract: In this paper, we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP), the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent 2-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or the quantifier specification. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time.
Url:
DOI: 10.1007/978-3-540-25984-8_26
Affiliations:
Links toward previous steps (curation, corpus...)
- to stream Istex, to step Corpus: 001D46
- to stream Istex, to step Curation: 001D25
- to stream Istex, to step Checkpoint: 001847
- to stream Main, to step Merge: 006F42
- to stream Main, to step Curation: 006C38
Le document en format XML
<record><TEI wicri:istexFullTextTei="biblStruct"><teiHeader><fileDesc><titleStmt><title xml:lang="en">Analyzing Selected Quantified Integer Programs</title><author><name sortKey="Subramani, K" sort="Subramani, K" uniqKey="Subramani K" first="K." last="Subramani">K. Subramani</name></author></titleStmt><publicationStmt><idno type="wicri:source">ISTEX</idno><idno type="RBID">ISTEX:7EE077499C911C17DB80D8027C634A98BB25E3B2</idno><date when="2004" year="2004">2004</date><idno type="doi">10.1007/978-3-540-25984-8_26</idno><idno type="url">https://api.istex.fr/ark:/67375/HCB-81381HF5-L/fulltext.pdf</idno><idno type="wicri:Area/Istex/Corpus">001D46</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Corpus" wicri:corpus="ISTEX">001D46</idno><idno type="wicri:Area/Istex/Curation">001D25</idno><idno type="wicri:Area/Istex/Checkpoint">001847</idno><idno type="wicri:explorRef" wicri:stream="Istex" wicri:step="Checkpoint">001847</idno><idno type="wicri:doubleKey">0302-9743:2004:Subramani K:analyzing:selected:quantified</idno><idno type="wicri:Area/Main/Merge">006F42</idno><idno type="wicri:Area/Main/Curation">006C38</idno><idno type="wicri:Area/Main/Exploration">006C38</idno></publicationStmt><sourceDesc><biblStruct><analytic><title level="a" type="main" xml:lang="en">Analyzing Selected Quantified Integer Programs</title><author><name sortKey="Subramani, K" sort="Subramani, K" uniqKey="Subramani K" first="K." last="Subramani">K. Subramani</name><affiliation wicri:level="2"><country xml:lang="fr">États-Unis</country><placeName><region type="state">Virginie-Occidentale</region></placeName><wicri:cityArea>LCSEE, West Virginia University, Morgantown</wicri:cityArea></affiliation><affiliation wicri:level="1"><country wicri:rule="url">États-Unis</country></affiliation></author></analytic><monogr></monogr><series><title level="s" type="main" xml:lang="en">Lecture Notes in Computer Science</title><idno type="ISSN">0302-9743</idno><idno type="eISSN">1611-3349</idno><idno type="ISSN">0302-9743</idno></series></biblStruct></sourceDesc><seriesStmt><idno type="ISSN">0302-9743</idno></seriesStmt></fileDesc><profileDesc><textClass></textClass></profileDesc></teiHeader><front><div type="abstract" xml:lang="en">Abstract: In this paper, we introduce a problem called Quantified Integer Programming, which generalizes the Quantified Satisfiability problem (QSAT). In a Quantified Integer Program (QIP), the program variables can assume arbitrary integral values, as opposed to the boolean values that are assumed by the variables of an instance of QSAT. QIPs naturally represent 2-person integer matrix games. The Quantified Integer Programming problem is PSPACE-hard in general, since the QSAT problem is PSPACE-complete. We focus on analyzing various special cases of the general problem, with a view to discovering subclasses that are tractable. Subclasses of the general QIP problem are obtained by restricting either the constraint matrix or the quantifier specification. We show that if the constraint matrix is totally unimodular, the problem of deciding a QIP can be solved in polynomial time.</div></front></TEI><affiliations><list><country><li>États-Unis</li></country><region><li>Virginie-Occidentale</li></region></list><tree><country name="États-Unis"><region name="Virginie-Occidentale"><name sortKey="Subramani, K" sort="Subramani, K" uniqKey="Subramani K" first="K." last="Subramani">K. Subramani</name></region><name sortKey="Subramani, K" sort="Subramani, K" uniqKey="Subramani K" first="K." last="Subramani">K. Subramani</name></country></tree></affiliations></record>Pour manipuler ce document sous Unix (Dilib)
EXPLOR_STEP=$WICRI_ROOT/Wicri/Lorraine/explor/InforLorV4/Data/Main/Exploration
HfdSelect -h $EXPLOR_STEP/biblio.hfd -nk 006C38 | SxmlIndent | more
Ou
HfdSelect -h $EXPLOR_AREA/Data/Main/Exploration/biblio.hfd -nk 006C38 | SxmlIndent | more
Pour mettre un lien sur cette page dans le réseau Wicri
{{Explor lien
|wiki= Wicri/Lorraine
|area= InforLorV4
|flux= Main
|étape= Exploration
|type= RBID
|clé= ISTEX:7EE077499C911C17DB80D8027C634A98BB25E3B2
|texte= Analyzing Selected Quantified Integer Programs
}}
| This area was generated with Dilib version V0.6.33. |  |